import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;


public class deque<T> implements Deque<T> {
	
	private int length = 0;
	private Node<T> head;
	private Node<T> tail;
	
	public T get(int index) {
		Node<T> current_node;

		if (index >= 0) {
			current_node = head;
			while (index > 0) {
				current_node = current_node.getNext();
				index -= 1;
			}
		}
		else {
			current_node = tail;
			index += 1;
			while (index < 0) {
				current_node = current_node.getPrev();
				index += 1;
			}
		}
		
		return current_node.getValue();
	}
	
	public String toString() {
		StringBuilder buffer = new StringBuilder("[");
		Iterator<T> iter = iterator();
		
		while (iter.hasNext()) {
			T value = iter.next();
			buffer.append(value.toString());
			if (iter.hasNext())
				buffer.append(", ");
		}
		buffer.append("]");
		
		return buffer.toString();
	}
	
	/*
	 * Add to the tail.
	 * @see java.util.Deque#add(java.lang.Object)
	 */
	@Override
	public boolean add(T ob) {
		addLast(ob);
		return true;
	}
	
	@Override
	public void addFirst(T ob) {
		Node<T> node = new Node<T>(ob);
		node.setNext(head);
		if (tail == null)
			tail = node;
		else
			head.setPrev(node);
		head = node;
		length += 1;
	}
	
	@Override
	public void addLast(T ob) {
		Node<T> node = new Node<T>(ob);
		node.setPrev(tail);
		if (head == null)
			head = node;
		else
			tail.setNext(node);
		tail = node;
		length += 1;
	}
	
	@Override
	public boolean contains(Object ob) {
		for (T item : this) {
			if (item.equals(ob)) {
				return true;
			}
		}
		return false;
	}
	
	/*
	 * Iterate over the sequence in reverse order.
	 * @see java.util.Deque#descendingIterator()
	 */
	@Override
	public Iterator<T> descendingIterator() {
		// TODO
		// Might be able to implement using reflection and a generic iterator that takes in what getter to use to advance down the sequence.
		return null;
	}
	
	/*
	 * Peek at the head.
	 * @see java.util.Deque#element()
	 */
	@Override
	public T element() {
		return peekFirst();
	}
	
	@Override
	public T getFirst() {
		return peekFirst();
	}
	
	@Override
	public T getLast() {
		return peekLast();
	}
	
	@Override
	public Iterator<T> iterator() {
		/*
		 * Private iterator implementation.
		 */
		class DequeIterator<E> implements Iterator<E> {
			private Node<E> current_node;

			public DequeIterator(Node<E> start) {
				current_node = start;
			}
			
			@Override
			public boolean hasNext() {
				return current_node != null;
			}

			@Override
			public E next() {
				E value = current_node.getValue();
				current_node = current_node.getNext();
				return value;
			}

			/*
			 * Not implemented.
			 */
			@Override
			public void remove() {}
		}
		
		return new DequeIterator<T>(head);
	}
	
	/*
	 * Add to the tail.
	 * @see java.util.Deque#offer(java.lang.Object)
	 */
	@Override
	public boolean offer(T ob) {
		addLast(ob);
		return true;
	}
	
	@Override
	public boolean offerFirst(T ob) {
		addFirst(ob);
		return true;
	}
	
	@Override
	public boolean offerLast(T ob) {
		addLast(ob);
		return true;
	}
	
	/*
	 * Peek at the head.
	 * @see java.util.Deque#peek()
	 */
	@Override
	public T peek() {
		return peekFirst();
	}
	
	@Override
	public T peekFirst() {
		return head.getValue();
	}
	
	@Override
	public T peekLast() {
		return tail.getValue();
	}
	
	/*
	 * Remove and return the head.
	 * @see java.util.Deque#poll()
	 */
	@Override
	public T poll() {
		return removeFirst();
	}
	@Override
	public T pollFirst() {
		return removeFirst();
	}
	
	@Override
	public T pollLast() {
		return removeLast();
	}
	
	@Override
	public T pop() {
		return removeLast();
	}
	
	/*
	 * Add to the head.
	 * @see java.util.Deque#push(java.lang.Object)
	 */
	@Override
	public void push(T ob) {
		addFirst(ob);
	}
	
	/*
	 * Removes and returns the head.
	 * @see java.util.Deque#remove()
	 */
	@Override
	public T remove() {
		return removeFirst();
	}
	
	@Override
	public boolean remove(Object ob) {
		// XXX
		return false;
	}
	
	@Override
	public T removeFirst() {
		T value = head.getValue();
		head = head.getNext();
		if (head == null)
			tail = null;
		else
			head.removePrev();
		length -= 1;
		return value;
	}

	@Override
	public boolean removeFirstOccurrence(Object arg0) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public T removeLast() {
		T value = tail.getValue();
		tail = tail.getPrev();
		if (tail == null)
			head = null;
		else
			tail.removeNext();
		length -= 1;
		return value;
	}

	@Override
	public boolean removeLastOccurrence(Object arg0) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public int size() {
		return length;
	}

	@Override
	public boolean addAll(Collection<? extends T> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public void clear() {
		head = null;
		tail = null;
		length = 0;
		
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean isEmpty() {
		return length == 0;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public <E> E[] toArray(E[] a) {
		// TODO Auto-generated method stub
		return null;
	}
	
	public static void main(String argv[]) {
		int position = 0;
		deque<Integer> my_deque = new deque<Integer>();

		while (position < argv.length) {
			Object to_print = my_deque;
			String token = argv[position];
			
			if (token.equals("push_left")) {
				position += 1;
				int arg = new Integer(argv[position]);
				my_deque.addFirst(arg);
			}
			else if (token.equals("push_right")) {
				position += 1;
				int arg = new Integer(argv[position]);
				my_deque.addLast(arg);
			}
			else if (token.equals("pop_left")) {
				to_print = my_deque.removeFirst();
			}
			else if (token.equals("pop_right")) {
				to_print = my_deque.removeLast();
			}
			else if (token.equals("peek_left")) {
				to_print = my_deque.peekFirst();
			}
			else if (token.equals("peek_right")) {
				to_print = my_deque.peekLast();
			}
			else if (token.equals("length")) {
				to_print = my_deque.size();
			}
			else if (token.equals("contains")) {
				position += 1;
				int arg = new Integer(argv[position]);
				to_print = my_deque.contains(arg);
			}
			else if (token.equals("index")) {
				position += 1;
				int arg = new Integer(argv[position]);
				to_print = my_deque.get(arg);
			}
			else if (token.equals("repr"));
			
			System.out.println(to_print);
			position += 1;
		}
	}
}


class Node<T> {
	private Node<T> prev;
	private T value;
	private Node<T> next;
	
	public Node (T ob) {
		value = ob;
	}
	
	public T getValue() {
		return value;
	}
	
	public Node<T> getPrev() {
		return prev;
	}
	
	public void setPrev(Node<T> node) {
		prev = node;
	}
	
	public void removePrev() {
		setPrev(null);
	}
	
	public Node<T> getNext() {
		return next;
	}
	
	public void setNext(Node<T> node) {
		next = node;
	}
	
	public void removeNext() {
		setNext(null);
	}
}